package Array.easy;

/**
 * 1. 问题描述
 *      给你两个有序整数数组nums1 和 nums2，请你将 nums2 合并到nums1中，使 nums1 成为一个有序数组。
 *        说明：
 *        初始化nums1 和 nums2 的元素数量分别为m 和 n 。
 *        你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
 * 2. 算法分析
 *     1. 双指针+辅助数组（空间消耗比较大，算法思路简单，代码书写简单）
 *
 *     2. 双指针 但此时我们不需要引入额外的内存空间
 *          对上述的空间的一个优化，实际上我们只需要将num2中的元素在num1中找到合适的位置
 *          放置即可，但此时我们需要移动num1中的元素，这样势必会造成时间上的浪费
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 合并两个有序数组 {
    public static void main(String[] args) {

    }

    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = 0;  // 指向num1中有效元素
        int j = 0; // 指向num2中有效元素
        int count = 0; //  指向新的数组
        int[] ans = new int[n+m]; // 辅助数组
        while(i < m && j < n) {
            if (nums1[i] <= nums2[j]) {
                ans[count] = nums1[i];
                count++;
                i++;
            } else {
                ans[count] = nums2[j];
                count++;
                j++;
            }
        }
        if (i == m) {
            while (j < n) {
                ans[count] = nums2[j];
                j++;
                count++;
            }
        }
        if (j == n) {
            while (i < m) {
                ans[count] = nums2[i];
                count++;
                i++;
            }
        }
        for (int s = 0; s < ans.length; s++) {
            nums1[s] = ans[s];
        }
    }

    //
    public static void merge2(int[] num1, int m, int[] num2, int n) {
        int i = 0; // 指向num1
        int j = 0; // 指向num2
        while (j < n) { // 每次循环找到num2[j]在num1中的合适的位置并放置该元素
            while (i < m) {
                if (num1[i] < num2[j]) {
                    i++;
                }
                if (i == m) {
                    // 此时说明num2中最小的元素比num1中最大的元素还大，直接将num2中的元素一次添加到num1有效元素的末尾即可
                    int s = i;
                    while (s < n+m) {
                        num1[s] = num2[j];
                        s++;
                        j++;
                    }
                } else {
                    // 从当前位置移动数组num1

                }
            }
        }
    }
}
